package com.peng.leetcode.tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * PathSum5
 * 剑指 Offer 34. 二叉树中和为某一值的路径
 * https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
 * <p>
 * Created on 2022/12/3
 *
 * @author lupeng
 */
public class PathSum5 {

    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root == null) {
            return ans;
        }
        dfs(root, target, new ArrayDeque<>());
        return ans;
    }

    void dfs(TreeNode n, int target, ArrayDeque<Integer> q) {
        if (n == null) {
            return;
        }
        target -= n.val;
        q.offerLast(n.val);
        if (target == 0 && n.left == null && n.right == null) {
            ans.add(new ArrayList<>(q));
        }
        dfs(n.left, target, q);
        dfs(n.right, target, q);
        q.pollLast();
    }
}
